/*
 * @lc app=leetcode.cn id=1774 lang=typescript
 *
 * [1774] 最接近目标价格的甜点成本
 */

// @lc code=start

function closestCost(baseCosts: number[], toppingCosts: number[], target: number): number {
  let ans = Math.min(...baseCosts);
  const dfs = (total: number, idx: number, toppingCosts: number[], target: number): void => {
    // 当前遍历配料组合和目标的差值
    const diffTotal = Math.abs(total - target);
    // 当前最优方案和目标的差值
    const diffAns = Math.abs(ans - target);
    // 超过答案，不是成本较低的方案，跳出
    if (total - target > diffAns) return;

    if (diffAns > diffTotal) {
      // 当前方案更优，更新答案
      ans = total;
    } else if (diffAns === diffTotal) {
      // 选择较小的成本
      ans = Math.min(ans, total);
    }

    // 配料表遍历结束
    if (idx === toppingCosts.length) return;

    // 不选择当前配料
    dfs(total, idx + 1, toppingCosts, target);
    // 当前配料选择一份
    dfs(total + toppingCosts[idx], idx + 1, toppingCosts, target);
    // 当前配料选择两份
    dfs(total + toppingCosts[idx] * 2, idx + 1, toppingCosts, target);
  };

  // 深度遍历每一份主料
  for (const cost of baseCosts) {
    dfs(cost, 0, toppingCosts, target);
  }
  return ans;
}
// @lc code=end
